package easy;

public class Solution_1046 {
    public int lastStoneWeight(int[] stones) {
        /*List<Integer> list = new ArrayList<>();
        for (int stone : stones) {
            list.add(stone);
        }
        Collections.sort(list);
        for (int i = list.size() - 1; i > 0; i-=2) {
            int sub = list.get(i) - list.get(i - 1);
            if (sub>0) {

            }
        }*/
        int[] array = new int[1001];
        for (int stone : stones) {
            array[stone]++;
        }
        int pre = 0;
        for (int i = array.length - 1; i >= 0; ) {
            if (array[i] > 0) {
                array[i]--;
                if (pre == 0) {
                    pre = i;
                } else {
                    int sub = pre - i;
                    array[sub]++;
                    i = Math.max(sub, i);
                    pre = 0;
                }
            } else {
                i--;
            }
        }
        return pre;
    }

    public static void main(String[] args) {
        Solution_1046 model = new Solution_1046();
        System.out.println(model.lastStoneWeight(new int[]{2, 7, 4, 1, 8, 1}));
    }
}
